package leetcode.链表;

/**
 * 合并两个有序链表
 *
 * 为了不影响原链表，要通过new一个新链表的方式，继承原链表
 * 注意保存原链表的头
 *
 * 解答
 * 既然链表是有序的，问题就简单了，按照原来链表的顺序，将他们组合到第三个链表上即可
 *
 * 首先遍历两个链表，分别从list1、list2里面取出第一个元素 然后比较值的大小，小的或者相等的元素，
 * 将当前list1的值new出一个节点，然后放到新链表list3里面
 * 新链表list3的指针后移一位、list1的指针后移一位
 * 如果是list1 > list2的话，就把list2的值new出一个节点，然后放到新链表list3里面
 * 新链表list3的指针后移一位、list2的指针后移一位
 * 最后可能存在list1、list2偏大，某一个链表没有比较完，需要把剩下的加入到list3
 *
 * 注意
 * 使用list3的时候，由于list3的指针一直在后移。
 * 需要返回list3的头结点的话，需要在开始就保存一个指向list3的头指针
 */
public class Test21合并两个有序链表 {

    static class ListNode {

        int val;

        ListNode next;

        ListNode(int x) {
            val = x;
        }

    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 把原两个链表的内容放到第三个链表，最后返回第三个链表的 头
        ListNode l3 = new ListNode(0);
        ListNode head = l3;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                ListNode newNode = new ListNode(l1.val);
                l3.next = newNode;
                l3 = l3.next;
                // 因为是 l1 小一些，所以下一步需要将l1的指针后移
                l1 = l1.next;
            } else {
                ListNode newNode = new ListNode(l2.val);
                l3.next = newNode;
                l3 = l3.next;
                l2 = l2.next;
            }
        }
        // 可能存在l1、l2偏大，某一个链表没有比较完，需要把剩下的加入到l3
        while (l1 != null) {
            ListNode newNode = new ListNode(l1.val);
            l3.next = newNode;
            l3 = l3.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            ListNode newNode = new ListNode(l2.val);
            l3.next = newNode;
            l3 = l3.next;
            l2 = l2.next;
        }

        return head.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;

        ListNode l11 = new ListNode(1);
        ListNode l22 = new ListNode(3);
        ListNode l33 = new ListNode(4);
        l11.next = l22;
        l22.next = l33;

        ListNode ans = mergeTwoLists(l1, l11);
        while (ans != null) {
            System.out.print(ans.val);
            ans = ans.next;
        }
    }
}
